package sort;

import java.util.Arrays;

@SuppressWarnings("unchecked")
public class HeapSort {

    public static void sort(Comparable[] arr) {

        int n = arr.length;
        for (int i = n/2; i > 0; i--) {
            sink(arr, i, n);
        }
        System.out.println("after Sink:"+Arrays.toString(arr));
        while (n>0){
            exch(arr, 1, n--);
            sink(arr, 1, n);
        }
        System.out.println("after Sort:"+Arrays.toString(arr));

    }

    private static void sink(Comparable[] arr, int k, int n){
        while (2*k <= n){
            int child = 2*k;
            if (child<n && less(arr, child, child+1)){
                child++;
            }
            if (!less(arr, k, child)){
                break;
            }
            exch(arr, k, child);
            k = child;
        }
    }

    private static boolean less(Comparable[] arr, int i, int j) {
        return arr[i-1].compareTo(arr[j-1]) < 0;
    }

    private static void exch(Comparable[] arr, int i, int j){
        Comparable temp = arr[i-1];
        arr[i-1] = arr[j-1];
        arr[j-1] = temp;
    }


}
